

/**
 * CS1332 Ashwin Ram Spring 2010
 * HW2 BST.java
 * Cesar Gonzalez-Flores
 * 
 * Collaboration Statement
 * "I worked on the homework assignment alone, using only course materials."
 * 
 * Class Description
 * This class represents a simple Binary Search Tree with only the bare minimum of associated methods
 */

public class BST<K extends Comparable<K>> implements BinarySearchTree<K>{
	
	protected BinaryNode<K> root;
	
	public BST(){root=null;}
	
	/**
	 * Returns the root node of the tree, or null if none.
	 * @return a BinaryNode or null
	 */
	public BinaryNode<K> getRoot(){return root;}
	
	/**
	 * Is this an empty tree?
	 * @return true if so, false if not
	 */
	public boolean isEmpty(){if(root==null)return true; else return false;}
	
	/**
	 * Inserts a new value into the tree.
	 * @param c value to insert Remember that this value is just the raw data.
	 * You must encapsulate it in a BinaryNode
	 */
	public BSTNode<K> insert(BSTNode<K> parent, K c, boolean left, boolean dup){
		//first check if the tree is null
		BSTNode<K> child = new BSTNode<K>(c, dup);
		if(isEmpty())
		{
			root=new BSTNode<K>(c, dup);
		}
		else if(left)
		{
			parent.setLeftChild(child);
		}
		else if(!left)
		{
			parent.setRightChild(child);
		}
		child.setParent(parent);
		return child;
	}//end method insert
	
	/**
	 * Look up an element in the tree.
	 * If an object which is equal (i.e., compareTo is 0) 
	 * exists in the tree, we return that object. Otherwise, we return null.
	 * @param c value to find
	 * @return the element in the tree, or null
	 */
	public BinaryNode<K> find(K c){
		BinaryNode<K> result=find(root,c);
		if(result==null) return null;
		return result;
	}//end method find
	
	public BinaryNode<K> find(BinaryNode<K> node,K c){
		//`check that the node isnt empty (object not found)
		if(node==null) return null;
		//check if c is to the left of the current node
		else if(c.compareTo(node.getData())<0){return find(node.getLeftChild(),c);}
		//check if c is to the right of the current node
		else if(c.compareTo(node.getData())>0){return find(node.getRightChild(),c);}
		//current node must contain the data being searched for
		else if(node.getDuplicate())
		{
				return null;
		}
		return node;
	}//end method find
	
	/**
	 * Remove an element in the tree.
	 * REALLY IMPORTANT: You will need to use the 3-Case Successor approach.
	 * For details on the 3-Case Successor please check the Homework write up (doc file)
	 * @param c value to remove
	 * @return true if the values were removed, false otherwise
	 */
	public boolean remove(K c){
		BinaryNode<K> target=remove(root,c);
		if(target==null) return false; else return true;
	}//end method remove
	
	public BinaryNode<K> remove(BinaryNode<K> node, K c){
		//target not found
		if(node==null) {return null;}
		//move left to search for the target
		else if(c.compareTo(node.getData())<0){node.setLeftChild(remove(node.getLeftChild(),c));}
		//move right to search for the target
		else if(c.compareTo(node.getData())>0){node.setRightChild(remove(node.getRightChild(),c));}
		//target for deletion has been found, cons
		else if(node.getLeftChild()==null){node=node.getRightChild();}
		else if(node.getRightChild()==null){node=node.getLeftChild();}
		else {
			node.setData(findMin(node.getRightChild()).getData());
			node.setRightChild(remove(node.getRightChild(),node.getData()));
		}
		return node;
	}//end method remove
	
	public BinaryNode<K> findMin(BinaryNode<K> node){
		BinaryNode<K> probe=node;
		while(probe.getLeftChild()!=null){probe=probe.getLeftChild();}
		return probe;
	}//end method findMin
	
	public void printPreOrder(BinaryNode<K> node){
		if(node==null) return;
		System.out.print(node.getData()+" ");
		printPreOrder(node.getLeftChild());
		printPreOrder(node.getRightChild());
	}//end method printPreOrder
	
	public void printInOrder(BinaryNode<K> node){
		if(node==null) return;	
		printInOrder(node.getLeftChild());
		System.out.print(node.getData()+" ");
		printInOrder(node.getRightChild());
	}//end method printInOrder
	
	public void setRoot(BSTNode<K> root)
	{
		this.root=root;
	}
}// end class BST